#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;
#define int long long

//struct node{
//	int val, depth;
//	bool operator<(const node& x)const {
//		if (val != x.val)
//			return x.val < val;
//		else
//			return x.depth < depth;
//	}
//};
//
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int n, k;
//	cin >> n >> k;
//	priority_queue<node> q;
//	for (int i = 0,w; i < n; i++) {
//		cin >> w;
//		q.push({ w,0 });
//	}
//	while ((n - 1) % (k - 1)) {
//		q.push({ 0,0 });
//		n++;
//	}
//	int ans = 0;
//
//	while (q.size() >= k) {
//		int tmp = 0;
//		int dp = 0;
//		for (int i = 1; i <= k; i++) {
//			tmp += q.top().val;
//			dp = max(dp, q.top().depth);
//			q.pop();
//		}
//		ans += tmp;
//		q.push({ tmp,dp + 1 });
//	}
//	cout << ans << '\n' << q.top().depth << '\n';
//	return 0;
//}


//int a[100005], d[100005];
//int pre[100005], nxt[100005];
//int del[100005];
//struct cmp{
//	bool operator()(int x, int y) {
//		return d[x] > d[y];	
//	}
//};
//void solve() {
//	int n, k;
//	cin >> n >> k;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//	}
//priority_queue<int, vector<int>, greater<int>>q;
//	for (int i = 1; i < n; i++) {
//		pre[i] = i - 1;
//		nxt[i] = i + 1;
//		d[i] = a[i + 1] - a[i];
//		q.push(i);
//	}
//	d[n] = 1e9;
//	pre[1] = nxt[n - 1] = n;
//	int ans = 0;
//	while (k--) {
//		int x = q.top(); q.pop();
//		while (del[x]) {
//			x = q.top();
//			q.pop();
//		}
//		ans += d[x];
//		del[pre[x]] = del[nxt[x]] = -1;
//		d[x] = d[pre[x]] + d[nxt[x]] - d[x];
//		q.push(x);
//		pre[x] = pre[pre[x]];
//		nxt[x] = nxt[nxt[x]];
//		nxt[pre[x]] = x;
//		pre[nxt[x]] = x;
//
//	}
//	cout << ans << '\n';
//}
//
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	solve();
//
//	return 0;
//}